package easy;

import java.util.Arrays;

public class Solution_1005 {

    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < k && i < nums.length; i++, count++) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
            } else {
                break;
            }
        }

        if (count < k) {
            int index = 0;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] < nums[index]) {
                    index = i;
                }
            }
            if ((k - count) % 2 == 1) {
                nums[index] = -nums[index];
            }
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }

    public static void main(String[] args) {
        Solution_1005 model = new Solution_1005();
        System.out.println(model.largestSumAfterKNegations(new int[]{-4, -2, -3}, 4));
        System.out.println(model.largestSumAfterKNegations(new int[]{-2, 9, 9, 8, 4}, 5));
        System.out.println(model.largestSumAfterKNegations(new int[]{4, 2, 3}, 1));
        System.out.println(model.largestSumAfterKNegations(new int[]{3, -1, 0, 2}, 3));
        System.out.println(model.largestSumAfterKNegations(new int[]{2, -3, -1, 5, -4}, 2));
    }
}
